home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Night Owl 6
/
Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso
/
016a
/
gofer221.zip
/
CH09
< prev
next >
Wrap
Text File
|
1991-11-20
|
38KB
|
1,057 lines
Introduction to Gofer 9. MORE ABOUT VALUE DECLARATIONS
9. MORE ABOUT VALUE DECLARATIONS
9.1 Simple pattern matching
----------------------------
Although the Gofer standard prelude includes many useful functions, you
will usually need to define a collection of new functions for specific
problems and calculations. The declaration of a function "f" usually
takes the form of a number of equations of the form:
f <pat1> <pat2> ... <patn> = <rhs>
(or an equivalent expression, if "f" is written as by an operator
symbol). Each of the expressions <pat1>, <pat2>, ..., <patn>
represents an argument to the function "f" and is called a `pattern'.
The number of such arguments is called the arity of "f". If "f" is
defined by more than one equation then they must be entered together
and each one must give the same arity for "f".
When a function is defined by more than one equation, it will usually
be necessary to evaluate one or more of the arguments to the function
to determine which equation applies. This process is called
`pattern-matching'. In all of the previous examples we have used only
the simplest kind of pattern -- a variable. As an example, consider
the factorial function defined in section 5:
fact n = product [1..n]
If we then wish to evaluate the expression "fact 6" we first match the
expression "6" against the pattern "n" and then evaluate the expression
obtained from "product [1..n]" by replacing the variable "n" with the
expression "6". The process of matching the arguments of a function
against the patterns in its definition and obtaining another expression
to be evaluated is called a `reduction'. Using Gofer, it is easy to
verify that the evaluation of "fact 6" takes one more reduction than
that of "product [1..6]":
? fact 6
720
(57 reductions, 85 cells)
? product [1..6]
720
(56 reductions, 85 cells)
?
Many kinds of constants such as the boolean values True and False can
also be used in patterns, as in the following definition of the
function "not" taken from the standard prelude:
not True = False
not False = True
In order to determine the value of an expression of the form "not b",
we must first evaluate the expression "b". If the result is "True"
then we use the first equation and the value of "not b" will be
"False". If the value of "b" is "False", then the second equation is
used and the value of "not b" will be "True".
21
Introduction to Gofer 9.1 Simple pattern matching
Other constants, including integers, characters and strings may also be
used in patterns. For example, if we define a function "hello" by:
hello "Mark" = "Howdy"
hello name = "Hello " ++ name ++ ", nice to meet you!"
then:
? hello "Mark"
Howdy
(1 reduction, 12 cells)
? hello "Fred"
Hello Fred, nice to meet you!
(13 reductions, 66 cells)
?
Note that the order in which the equations are written is very
important because Gofer always uses the first applicable equation. If
instead we had defined the function with the equations:
hello name = "Hello " ++ name ++ ", nice to meet you!"
hello "Mark" = "Howdy"
then the results obtained using this function would have been a little
different:
? hello "Mark"
Hello Mark, nice to meet you!
(13 reductions, 66 cells)
? hello "Fred"
Hello Fred, nice to meet you!
(13 reductions, 66 cells)
?
There are a number of other useful kinds of pattern, some of which are
illustrated by the following examples:
o Wildcard: _ matches any value at all; it is like a
variable pattern, except that there is no
way of referring to the matched value.
o Tuples: (x,y) matches a pair whose first and second
elements are called x and y respectively.
o Lists: [x] matches a list with precisely one element
called x.
[_,2,_] matches a list with precisely three
elements, the second of which is the
integer 2.
[] matches the empty list.
(x:xs) matches a non-empty list with head x and
tail xs.
o As patterns: p@(x,y) matches a pair whose first and second
components are called x and y. The
complete pair can also be referred to
22
Introduction to Gofer 9.1 Simple pattern matching
directly as p.
o (n+k) patterns: (m+1) matches an integer value greater than or
equal to 1. The value referred to by the
variable m is one less than the value
matched.
A further kind of pattern (called an irrefutable pattern) is introduced
in section 9.11.
Note that no variable name can be used more than once on the left hand
side of each equation in a function definition. The following example:
areTheyTheSame x x = True
areTheyTheSame _ _ = False
will not be accepted by the Gofer system, but should instead be defined
using the notation of guards introduced in the next section:
areTheyTheSame x y
| x==y = True
| otherwise = False
9.2 Guarded equations
----------------------
Each of the equations in a function definition may contain `guards'
which require certain conditions on the values of the functions's
arguments to be met. As an example, here is a function which uses the
standard prelude function even :: Int -> Bool to determine whether its
argument is an even integer or not, and returns the string "even" or
"odd" as appropriate:
oddity n | even n = "even"
| otherwise = "odd"
In general, an equation using guards takes the form:
f x1 x2 ... xn | condition1 = e1
| condition2 = e2
.
.
| conditionm = em
This equation is used by evaluating each of the conditions in turn
until one of them evaluates to "True", in which case the value of the
function is given by the corresponding expression e on the right hand
side of the `=' sign. In Gofer, the variable "otherwise" is defined to
be equal to "True", so that writing "otherwise" as the condition in a
guard means that the corresponding expression will always be used if no
previous guard has been satisfied.
[ASIDE: in the notation of [1], the above examples would be written as:
oddity n = "even", if even n
= "odd", otherwise
23
Introduction to Gofer 9.2 Guarded equations
f x1 x2 ... xn = e1, if condition1
= e2, if condition2
.
.
= em, if conditionm
Translation between the two notations is relatively straightforward.]
9.3 Local definitions
----------------------
Function definitions may include local definitions for variables which
can be used both in guards and on the right hand side of an equation.
Consider the following function which calculates the number of distinct
real roots for a quadratic equation of the form a*x*x + b*x + c = 0:
numberOfRoots a b c | discr>0 = 2
| discr==0 = 1
| discr<0 = 0
where discr = b*b - 4*a*c
[ASIDE: The operator (==) is used to test whether two values are equal
or not. You should take care not to confuse this with the single `='
sign used in function definitions].
Local definitions can also be introduced at an arbitrary point in an
expression using an expression of the form:
let <decls> in <expr>
For example:
? let x = 1 + 4 in x*x + 3*x + 1
41
(8 reductions, 15 cells)
? let p x = x*x + 3*x + 1 in p (1 + 4)
41
(7 reductions, 15 cells)
?
9.4 Recursion with integers
----------------------------
Recursion is a particularly important and powerful technique in
functional programming which is useful for defining functions involving
a wide range of datatypes. In this section, we describe one particular
application of recursion to give an alternative definition for the
factorial function from section 5.
Suppose that we wish to calculate the factorial of a given integer n.
We can split the problem up into two special cases:
o If n is zero then the value of n! is 1.
o Otherwise, n! = 1 * 2 * ... * (n-1) * n = (n-1)! * n and so we
can calculate the value of n! by calculating the value of (n-1)!
24
Introduction to Gofer 9.4 Recursion with integers
and then multiplying it by n.
This process can be expressed directly in Gofer using a conditional
expression:
fact1 n = if n==0 then 1 else n * fact1 (n-1)
This definition may seem rather circular; in order to calculate the
value of n!, we must first calculate (n-1)!, and unless n is 1, this
requires the calculation of (n-2)! etc... However, if we start with
some positive value for the variable n, then we will eventually reach
the case where the value of 0! is required -- and this does not require
any further calculation. The following diagram illustrates how 6! is
evaluated using "fact1":
fact1 6 ==> 6 * fact1 5
==> 6 * (5 * fact1 4)
==> 6 * (5 * (4 * fact1 3))
==> 6 * (5 * (4 * (3 * fact1 2)))
==> 6 * (5 * (4 * (3 * (2 * fact1 1))))
==> 6 * (5 * (4 * (3 * (2 * (1 * fact1 0)))))
==> 6 * (5 * (4 * (3 * (2 * (1 * 1)))))
==> 6 * (5 * (4 * (3 * (2 * 1))))
==> 6 * (5 * (4 * (3 * 2)))
==> 6 * (5 * (4 * 6))
==> 6 * (5 * 24)
==> 6 * 120
==> 720
Incidentally, there are several other ways of writing the recursive
definition of "fact1" above in Gofer. For example, using guards:
fact2 n
| n==0 = 1
| otherwise = n * fact2 (n-1)
or using pattern matching with an integer constant:
fact3 0 = 1
fact3 n = n * fact3 (n-1)
Which of these you use is largely a matter of personal taste.
Yet another style of definition uses the (n+k) patterns mentioned in
section 9.1:
fact4 0 = 1
fact4 (n+1) = (n+1) * fact4 n
which is equivalent to:
fact5 n | n==0 = 1
| n>=1 = n * fact5 (n-1)
[COMMENT: Although each of the above definitions gives the same result
as the original "fact" function for each non-negative integer, the
25
Introduction to Gofer 9.4 Recursion with integers
functions can still be distinguished by the values obtained when they
are applied to negative integers:
o "fact (-1)" evaluates to the integer 1.
o "fact1 (-1)" causes Gofer to enter an infinite loop, which is only
eventually terminated when Gofer runs out of `stack space'.
o "fact4 (-1)" causes an evaluation error and prints the
message {fact4 (-1)} on the screen.
To most people, this suggests that the definition of "fact4" is perhaps
preferable to that of either "fact" or "fact1" as it neither gives the
wrong answer without allowing this to be detected nor causes a
potentially non-terminating computation.]
9.5 Recursion with lists
-------------------------
The same kind of technique that can be used to define recursive
functions with integers can also be used to define recursive functions
on lists. As an example, suppose that we wish to define a function to
calculate the length of a list. As the standard prelude already
includes such a function called "length", we will call the function
developed here "len" to avoid any conflict. Now suppose that we wish
to find the length of a given list. There are two cases to consider:
o If the list is empty then it has length 0
o Otherwise, it is non-empty and can be written in the form (x:xs)
for some element x and some list xs. Thus the original list is
one element longer than xs, and so has length 1 + len xs.
Writing these two cases out leads directly to the following definition:
len [] = 0
len (x:xs) = 1 + length xs
The following diagram illustrates the way that this function can be
used to determine the length of the list [1,2,3,4] (remember that this
is just an abbreviation for 1 : 2 : 3 : 4 : []):
len [1,2,3,4] ==> 1 + len [2,3,4]
==> 1 + (1 + len [3,4])
==> 1 + (1 + (1 + len [4]))
==> 1 + (1 + (1 + (1 + len [])))
==> 1 + (1 + (1 + (1 + 0)))
==> 1 + (1 + (1 + 1))
==> 1 + (1 + 2)
==> 1 + 3
==> 4
As further examples, you might like to look at the following
definitions which use similar ideas to define the functions product and
map introduced in earlier sections:
product [] = 1
product (x:xs) = x * product xs
26
Introduction to Gofer 9.5 Recursion with lists
map f [] = []
map f (x:xs) = f x : map f xs
9.6 Lazy evaluation
--------------------
Gofer evaluates expressions using a technique sometimes described as
`lazy evaluation' which means that:
o No expression is evaluated until its value is needed.
o No shared expression is evaluated more than once; if the
expression is ever evaluated then the result is shared between all
those places in which it is used.
The first of these ideas is illustrated by the following function:
ignoreArgument x = "I didn't need to evaluate x"
Since the result of the function "ignoreArgument" doesn't depend on the
value of its argument "x", that argument will not be evaluated:
? ignoreArgument (1/0)
I didn't need to evaluate x
(1 reduction, 31 cells)
?
In some situations, it is useful to be able to force Gofer to evaluate
the argument to a function before the function is applied. This can be
achieved using the function "strict" defined in the standard prelude;
An expression of the form "strict f x" is evaluated by first evaluating
the argument "x" and then applying the function "f" to the result:
? strict ignoreArgument (1/0)
{primDivInt 1 0}
(4 reductions, 29 cells)
?
The second basic idea behind lazy evaluation is that no shared
expression should be evaluated more than once. For example, the
following two expressions can be used to calculate 3*3*3*3:
? square * square where square = 3 * 3
81
(3 reductions, 9 cells)
? (3 * 3) * (3 * 3)
81
(4 reductions, 11 cells)
?
Notice that the first expression requires one less reduction than the
second. Excluding the single reduction step needed to convert each
integer into a string, the sequences of reductions that will be used in
each case are as follows:
27
Introduction to Gofer 9.6 Lazy evaluation
square * square where square = 3 * 3
-- calculate the value of square by reducing 3 * 3 ==> 9
-- and replace each occurrence of square with this result
==> 9 * 9
==> 81
(3 * 3) * (3 * 3) -- evaluate first (3 * 3)
==> 9 * (3 * 3) -- evaluate second (3 * 3)
==> 9 * 9
==>
Lazy evaluation is a very powerful feature of programming in a language
like Gofer, and means that only the minimum amount of calculation is
used to determine the result of an expression. The following example
is often used to illustrate this point.
Consider the task of finding the smallest element of a list of
integers. The standard prelude includes a function "minimum" which can
be used for this very purpose:
? minimum [100,99..1]
1
(809 reductions, 1322 cells)
?
(The expression [100,99..1] denotes the list of integers from 1 to 100
arranged in decreasing order, as described in section 10.1).
A rather different approach involves sorting the elements of the list
into increasing order (using the function "sort" defined in the
standard prelude) and then take the element at the head of the
resulting list (using the standard function "head"). Of course,
sorting the list in its entirity is likely to require significantly
more work than the previous approach:
? sort [100,99..1]
[1, 2, 3, 4, 5, 6, 7, 8, ... etc ..., 99, 100]
(10712 reductions, 21519 cells)
?
However, thanks to lazy-evaluation, calculating just the first element
of the sorted list actually requires less work in this particular case
than the first solution using "minimum":
? head (sort [100,99..1])
1
(713 reductions, 1227 cells)
?
Incidentally, it is probably work pointing out that this example
depends rather heavily on the particular algorithm used to "sort" a
list of elements. The results are rather different if we compare the
same two approaches used to calculate the maximum value in the list:
? maximum [100,99..1]
100
28
Introduction to Gofer 9.6 Lazy evaluation
(812 reductions, 1225 cells)
? last (sort [100,99..1])
100
(10612 reductions, 20732 cells)
?
This difference is caused by the fact that each element in the list
produced by "sort" is only known once the values of all of the
preceding elements are also known. Thus the complete list must be
sorted in order to obtain the last element.
9.7 Infinite data structures
-----------------------------
One particular benefit of lazy evaluation is that it makes it possible
for functions in Gofer to manipulate `infinite' data structures.
Obviously we cannot hope to either construct or store an infinite
object in its entirity -- the advantage of lazy evaluation is that it
allows us to construct infinite objects piece by piece as necessary
(and to reuse the storage space used by parts of the object when they
are no longer required).
As a simple example, consider the following function which can be used
to produce infinite lists of integer values:
countFrom n = n : countFrom (n+1)
If we evaluate the expression "countFrom 1", Gofer just prints the list
of integer values beginning with 1 until it is interrupted. Once each
element in the list has been printed, the storage used to hold that
element can be reused to hold later elements in the list. Evaluating
this expression is equivalent to using an `infinite' loop to print the
list of integers in an imperative programming language:
? countFrom 1
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,^C{Interrupted!}
(53 reductions, 160 cells)
?
For practical applications, we are usually only interested in using a
finite portion of an infinite data structure (just as loops in an
imperative programming language are usually terminated after finitely
many iterations). For example, using "countFrom" together with the
function "take" defined in the standard prelude, we can repeat the
calculation from section 4 to find the sum of the integers 1 to 10:
? sum (take 10 (countFrom 1))
55
(62 reductions, 119 cells)
?
[ASIDE: The expression "take n xs" evaluates to a list containing the
first n elements of the list xs (or to xs itself if the list contains
fewer than n elements). Thus "countFrom 1" generates the infinite list
of integers, "take 10" ensures that only the first ten elements are
calculated, and "sum" calculates the sum of those integers as before.]
29
Introduction to Gofer 9.7 Infinite data structures
A particular advantage of using infinite data structures is that it
enables us to describe an object without being tied to one particular
application of that object. Consider the following definition for the
infinite list of powers of two [1, 2, 4, 8, ...]:
powersOfTwo = 1 : map double powersOfTwo
where double n = 2*n
This list be used in a variety of ways; using the operator (!!) defined
in the standard prelude [xs!!n evaluates to the nth element of the list
xs], we can define a function to find the nth power of 2 for an given
integer n:
twoToThe n = powersOfTwo !! n
Alternatively, we can use the list "powersOfTwo" to define a function
mapping lists of bits (represented by integers 0 and 1) to the
corresponding decimal number: simply reverse the order of the digits,
multiply each by the corresponding power of two and calculate the sum.
Using functions from the standard prelude, this translates directly
into the definition:
binToDec ds = sum (zipWith (*) (reverse ds) powersOfTwo)
For example:
? twoToThe 12
4096
(15 reductions, 21 cells)
? binToDec [1,0,1,1,0]
22
(40 reductions, 85 cells)
?
9.8 Polymorphism
-----------------
Given the definition of "product" in section 9.5, it is easy to see
that product takes a single argument which is a list of integers and
returns a single integer value -- the product of the elements of the
list. In other words, "product" has type [Int] -> Int. On the other
hand, it is not immediately clear what the type of the function "map"
should be. Clearly the first argument of "map" must be a function and
both the second argument and the result are lists, so that the type of
"map" must be of the form:
(a -> b) -> [c] -> [d]
\______/ \___/ \___/
type of 1st type of 2nd type of result
argument "f" argument "xs" "map f xs"
But what can be said about the types a, b, c and d? One possibility
would be to choose a = b = c = d = Int which would be acceptable for
expressions such as "map fact [1,2,3,4]", but this would not be
suitable in an expression such as "map chr [65,75,32]" because the
"chr" function does not have type Int -> Int.
30
Introduction to Gofer 9.8 Polymorphism
Notice however that the argument type of "f" must be the same as the
type of elements in the second argument (i.e. a = c) since "f" is
applied to each element in that list. Similarly, the result type of
"f" must be the same as the type of elements in the result list (i.e. b
= d) since each element in this list is obtained as a result of
applying the function "f" to some value. It is therefore reasonable to
treat the "map" function as having any type of the form:
(a -> b) -> [a] -> [b]
The letters "a" and "b" used in this type expression represent
arbitrary types and are called type variables. An object whose type
includes one or more type variables can be thought of as having many
different types and is often described as having a `polymorphic type'
(literally: its type has `many shapes').
The ability to define and use polymorphic functions in Gofer turns out
to be very useful. Here are the types of some of the other polymorphic
functions which have been used in previous examples which illustrate
this point:
length :: [a] -> Int
(++) :: [a] -> [a] -> [a]
concat :: [[a]] -> [a]
Thus we can use precisely the same "length" function to determine both
the length of a list of integers as well as finding the length of a
string:
? length [1..10]
10
(98 reductions, 138 cells)
? length "Hello"
5
(22 reductions, 36 cells)
?
9.9 Higher-order functions
---------------------------
In Gofer, function values are treated in much the same way as any other
kind of value; in particular, they can be used both as arguments to,
and results of other functions.
Functions which manipulate other functions in this way are often
described as `higher-order functions'. Consider the following example,
taken from the standard prelude:
(.) :: (b -> c) -> (a -> b) -> (a -> c)
(f . g) x = f (g x)
As indicated by the type declaration, we think of the (.) operator as a
function taking two function arguments and returning another function
value as its result. If f and g are functions of the appropriate
types, then (f . g) is a function called the composition of f with g.
Applying (f . g) to a value is equivalent to applying g to that value,
31
Introduction to Gofer 9.9 Higher-order functions
and then applying f to the result [As described, far more eloquently,
by the second line of the declaration above!].
Many problems can often be described very elegantly as a composition of
other functions. Consider the problem of calculating the total number
of characters used in a list of strings. A simple recursive function
provides one solution:
countChars [] = 0
countChars (w:ws) = length w + countChars ws
? countChars ["super","cali","fragi","listic"]
20
(96 reductions, 152 cells)
?
An alternative approach is to notice that we can calculate the total
number of characters by first combining all of the words in the
argument list into a single word (using concat) and then finding the
length of that word:
? (length . concat) ["super","cali","fragi","listic"]
20
(113 reductions, 211 cells)
?
Another solution is to first find the length of each word in the list
(using the "map" function to apply "length" to each word) and then
calculate the sum of these individual lengths:
? (sum . map length) ["super","cali","fragi","listic"]
20
(105 reductions, 172 cells)
?
9.10 Variable declarations
--------------------------
A variable declaration is a special form of function definition,
almost always consisting of a single equation of the form:
var = rhs
(i.e. a function declaration of arity 0). Whereas the values defined
by function declarations of arity>0 are guaranteed to be functions, the
values defined by variable declarations may or may not be functions:
odd = not . even -- if an integer is not even then it must be odd
val = sum [1..100]
Note that variables defined like this at the top level of a file of
definitions will be evaluated using lazy evaluation. The first time we
refer to the variable "val" defined above (either directly or
indirectly), Gofer evaluates the sum of the integers from 1 to 100 and
overwrites the definition of "val" with this number. This calculation
can then be avoided for each subsequent use of "val" (unless the file
32
Introduction to Gofer 9.10 Variable declarations
containing the definition of "val" is reloaded).
? val
5050
(809 reductions, 1120 cells)
? val
5050
(1 reduction, 7 cells)
?
Because of this behaviour, should probably try to avoid using variable
declarations where the resulting value will require a lot of storage
space. If we load a file of definitions including the line:
longList = [1..10000]
and then evaluate the expression "length longList" (eventually
obtaining the expected result of 10000), then Gofer will evaluate the
definition of "longList" and replace it with the complete list of
integers from 1 upto 10000. Unlike other memory used during a
calculation, it will not be possible to reuse this space for other
calculations without reloading the file defining "longList", or loading
other files instead.
9.11 Pattern bindings and irrefutable patterns
----------------------------------------------
Another useful way of defining variables uses `pattern bindings' which
are equations of the form:
pat = rhs
where the expression on the left hand side is a pattern as described in
section 9.1. As a simple example of pattern bindings, here is one
possible definition for the function "head" which returns the first
element in a list of values:
head xs = x where (x:ys) = xs
[The definition "head (x:_) = xs" used in the standard prelude is
slightly more efficient, but otherwise equivalent.]
[ASIDE: Note that pattern bindings are treated quite differently from
function bindings (of which the variable declarations described in the
last section are a special case). There are two situations in which an
ambiguity may occur; i.e. if the left hand side of an equation is a
simple variable or an (n+k) pattern of the kind described in section
9.1. In both cases, these are treated as function bindings, the former
being a variable declaration whilst the latter will be treated as a
definition for the operator symbol (+).]
Pattern bindings are often useful for defining functions which we might
think of as `returning more than one value' -- although they are
actually packaged up in a single value such as a tuple. As an example,
33
Introduction to Gofer 9.11 Pattern bindings and irrefutable patterns
consider the function "span" defined in the standard prelude.
span :: (a -> Bool) -> [a] -> ([a],[a])
If xs is a list of values and p is a predicate, then span p xs returns
the pair of lists (ys,zs) such that ys++zs == xs, all of the elements
in ys satisfy the predicate p and the first element of zs does not
satisfy p. A suitable definition, using a pattern binding to obtain
the two lists resulting from the recursive call to "span" is as
follows:
span p [] = ([],[])
span p xs@(x:xs')
| p x = let (ys,zs) = span p xs' in (x:ys,zs)
| otherwise = ([],xs)
For consistency with the lazy evaluation strategy used in Gofer, the
right hand side of a pattern binding is not evaluated until the value
of one of the variables bound by that pattern is required. The
definition:
(0:xs) = [1,2,3]
will not cause any errors when it is loaded into Gofer, but will cause
an error if we attempt to evaluate the variable xs:
? xs
{v120 [1, 2, 3]}
(11 reductions, 46 cells)
?
The variable name "v120" appearing in this expression is the name of a
function called a `conformality check' which is defined automatically
by Gofer to ensure that the value on the right hand side of the pattern
binding conforms with the pattern on the left.
Compare this with the behaviour of pattern matching in function
definitions such as:
? example [1] where example (0:xs) = "Hello"
{v126 [1]}
(4 reductions, 22 cells)
?
where the equivalent of the conformality check is carried out
immediately even if none of the values of the variables in the pattern
are actually required. The reason for this difference is that the
arguments supplied to a function must be evaluated to determine which
equation in the definition of the function should be used. The error
produced by the example above was caused by the fact that the argument
[1] does not match the pattern used in the equation defining "example"
(represented by an internal Gofer function called "v126").
A different kind of behaviour can be obtained using a pattern of the
form ~pat, known as an irrefutable (or lazy) pattern. This pattern can
34
Introduction to Gofer 9.11 Pattern bindings and irrefutable patterns
initially be matched against any value, delaying the check that this
value does indeed match pat until the value of one of the variables
appearing in it is required. The basic idea (together with the method
used to implement irrefutable patterns in Gofer) is illustrated by the
identity:
f ~pat = rhs is equivalent to f v = rhs where pat=v
The following examples, based very closely on those given in the
Haskell report [5], illustrate the use of irrefutable patterns. The
variable "undefined" used in these examples is included in the standard
prelude and causes a run-time error each time it is evaluated
(technically speaking, it represents the bottom element of the relevant
semantic domain, and is the only value having all possible types):
(\ (x,y) -> 0) undefined = {undefined}
(\~(x,y) -> 0) undefined = 0
(\ [x] -> 0) [] = {v113 []}
(\~[x] -> 0) [] = 0
(\~[x, (a,b)] -> x) [(0,1),undefined] = {undefined}
(\~[x,~(a,b)] -> x) [(0,1),undefined] = (0,1)
(\ (x:xs) -> x:x:xs) undefined = {undefined}
(\~(x:xs) -> x:x:xs) undefined = {undefined}:{undefined}:{undefined}
Irrefutable patterns are not used very frequently, although they are
particularly convenient in some situations (see section 12 for some
examples). Be careful not to use irrefutable patterns where they are
not appropriate. An attempt to define a map function "map'" using:
map' f ~(x:xs) = f x : map' f xs
map' f [] = []
turns out to be equivalent to the definition:
map' f ys = f x : map f xs where (x:xs) = ys
and will not behave as you might have intended:
? map' ord "abc"
[97, 98, 99, {v124 []}, {v124 []}, {v^C{Interrupted!}
(35 reductions, 159 cells)
?
9.12 Type declarations
-----------------------
The type system used in Gofer is sufficiently powerful to enable Gofer
to determine the type of any function without the need to declare the
types of the its arguments and return value as in some programming
languages. Despite this, Gofer allows the use of type declarations of
the form:
var1, ..., varn :: type
35
Introduction to Gofer 9.12 Type declarations
which enable to programmer to declare the intended types of the
variables var1, ..., varn defined in either function or pattern
bindings. There are a number of benefits of including type
declarations of this kind in a program:
o Documentation: The type of a function often provides useful
information about the way in which a function is to be used --
including the number and order of its arguments.
o Restriction: In some situations, the type of a function inferred
by Gofer is more general than is required. As an example,
consider the following function, intended to act as the identity
on integer values:
idInt x = x
Without an explicit type declaration, Gofer treats "idInt" as a
polymorphic function of type a -> a and does not treat expression
such as "idInt 'A'" as a type error. This problem can be solved
by using an explicit type declaration to restrict the type of
"idInt" to a particular instance of the polymorphic type a -> a:
idInt :: Int -> Int
Note that an a declaration such as:
idInt :: Int -> a
is not a valid type for the function "idInt" (the value of the
expression "idInt 42" is an integer and cannot be treated as
having an arbitrary type, depending on the value of the type
variable "a"), and hence will not be accepted by Gofer.
o Consistency check: As illustrated above, declared types are always
checked against the definition of a value to make sure that they
are compatible. Thus Gofer can be used to check that the
programmers intentions (as described by the types assigned to
variables in type declarations) are consistent with the
definitions of those values.
o Overloading: Explicit type declarations can be used to solve a
number of problems associated with overloaded functions and
values. See section 14 for further details.
36
